package com.zlk.algorithm.dataStructure.linkList03;

/**
 * @program: algorithm
 * @ClassName Code10_1_LinkedListCycleII
 * @description:
 * @author: slfang
 * @create: 2024-12-15 16:31
 * @Version 1.0
 **/
// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
public class Code10_1_LinkedListCycleII {


    /// 方法1 可以用HashSet 容器方法
    //直接记这个流程 不用管流程
    // 首先快慢指针相遇
    // 然后f 回到原来head 位置
    // 然后s1步  f一步
    // 然后一定会在环的第一个节点相遇
    public static class ListNode {
        public int val;
        public ListNode next;
    }

    // 提交如下的方法
    public static ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        ListNode slow = head.next;
        ListNode fast = head.next.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
        
    }

}
